package backtracing;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: june
 * @date: 2023/7/26
 * @description: 216. 组合总和 III
 * 找出所有相加之和为n 的k个数的组合，且满足下列条件：
 * <p>
 * 只使用数字1到9
 * 每个数字最多使用一次
 * 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
 * <p>
 * 2 <= k <= 9
 * 1 <= n <= 60
 **/

public class CombinationSum_216 {

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        backtrace(k, n, 0, 1);
        return result;
    }

    private void backtrace(int k, int n, int sum, int startIndex) {
        // 剪枝
        if (sum > n) {
            return;
        }

        if (path.size() == k) {
            if (sum == n) {
                result.add(new ArrayList<>(path));
            }
            return;
        }

        for (int i = startIndex; i <= 9; i++) {
            path.add(i);
            sum += i;
            backtrace(k, n, sum, i + 1);
            // 回溯时，sum也要减去之前的值
            sum -= i;
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationSum_216 combinationSum_216 = new CombinationSum_216();
        List<List<Integer>> lists = combinationSum_216.combinationSum3(2, 6);
        System.out.println(lists);
    }
}
